package com.sxu.search.binary;

/**
 * 插值查找 - 基于二分查找的改进
 *  计算公式: mid = left + (target - arr[left]) * (right - left) / arr[right] - arr[left]
 *  时间复杂度：O（log logN） ~ O（N）
 *  空间复杂度：O（1）
 *  适用：分布均匀的序列
 */
public class InterpolationSearch {
    public static int interpolationSearch(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        while (left <= right && target >= arr[left] && target <= arr[right]) {
            // 处理特殊情况 避免分母为0
            if(arr[left] == arr[right]) {
                return arr[left] == target ? left : -1;
            }
            int mid = left + (target - arr[left]) * (right - left) / (arr[right] - arr[left]);
            // 限定mid在合法的范围内 mid必须在 left - right之间
            mid = Math.max(left,Math.min(right,mid));
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
}
